Skip to main content

Substring with Concatenation of All Words

Question​

Given a string s and a list of words words that are all of the same length, find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, and without any intervening characters.

Example 1
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]

Solution​

all//Substring with Concatenation of All Words.py


def substring_with_concatenation_of_all_words(s, words):
    if not s or not words:
        return []

    # Initialization
    length = len(words[0])
    word_dict = {word: words.count(word) for word in words}
    result = []

    for i in range(len(s) + 1 - length * len(words)):
        temp = s[i:i + length]
        if temp in words:
            seen = {temp: 1}
            j = i + length
            flag = True
            while j < len(s) + 1 and flag:
                temp = s[j:j + length]
                if temp not in words:
                    flag = False
                else:
                    seen[temp] = seen.get(temp, 0) + 1
                    if seen[temp] > word_dict[temp]:
                        flag = False
                j += length
            if flag:
                result.append(i)

    return result